﻿using System;
using System.Collections.Generic;
using System.Threading;
using log4net;

namespace Interactive.Utility.Collections
{
    /// <summary>
    /// 基于LFU淘汰算法Dictionary缓存结构。
    /// 比基于链表的LRU优势在于读取的性能。读取只是对计算器原子自增。
    /// 作为替代，回收内存的成本较高。因此采用批量回收的机制减少性能开销。
    /// 淘汰成本随容量递增。容量较大时应考虑使用LinkedHashMap以获得较稳定的性能。
    /// 该类线程安全。
    /// </summary>
    public class CounterDict<K, V> where V : class
    {
        private readonly Dictionary<K, Entry> dict;
        private readonly ILog log;
        private int capacity;
        private string name;
        private IList<KeyValuePair<K, V>> recycleList;
        private int recyclingQuantity;
        private Dictionary<K, Entry> tempDict;

        /// <param name="capacity">初始容量</param>
        /// <param name="comparer">键比较器</param>
        public CounterDict(int capacity, IEqualityComparer<K> comparer)
        {
            log = LogManager.GetLogger(GetType());

            dict = new Dictionary<K, Entry>(capacity, comparer);
            Capacity = capacity;
            RecyclingQuantity = capacity/10;
        }

        /// <param name="capacity">初始容量</param>
        public CounterDict(int capacity) : this(capacity, EqualityComparer<K>.Default)
        {
        }

        /// <summary>
        /// 缓存未命中的回调
        /// </summary>
        public CacheItemMissedCallback<K, V> CacheMissedHandler { get; set; }

        /// <summary>
        /// 缓存超过容量而被回收后的回调
        /// </summary>
        public CacheItemsRecycledCallback<K, V> CacheItemsRecycledHandler { get; set; }


        /// <summary>
        /// 设置或获取缓存的容量（不少于10）
        /// </summary>
        public int Capacity
        {
            get { return capacity; }
            set
            {
                if (value < 10)
                {
                    throw new ArgumentOutOfRangeException("value", "缓存的容量应该不少于10");
                }
                capacity = value;
            }
        }

        /// <summary>
        /// 名称。用于跟踪时的标识。
        /// </summary>
        public string Name
        {
            get { return "CounterDict:" + name; }
            set { name = value; }
        }

        /// <summary>
        /// 每次执行内存回收的移除的项数量
        /// </summary>
        public int RecyclingQuantity
        {
            get { return recyclingQuantity; }
            set
            {
                if (value < 1 || value > capacity/2)
                {
                    throw new ArgumentOutOfRangeException("value", "每次回收项数应介于1至容量的一半之间");
                }
                recyclingQuantity = value;
            }
        }

        /// <summary>
        /// 获取或设置一个缓存项。
        /// CacheMissedHandler未设置时，获取一个不存在的项将引发异常。
        /// 获取时如CacheMissedHandler回调返回Null，该项不加入缓存。
        /// </summary>
        /// <param name="key"></param>
        /// <exception cref="KeyNotFoundException" />
        /// <returns></returns>
        public V this[K key]
        {
            get
            {
                Entry entry;
                if (TryGetEntry(key, out entry))
                {
                    return entry.Value;
                }
                if (CacheMissedHandler != null)
                {
                    V value = CacheMissedHandler(key);
                    if (value != default(V))
                    {
                        this[key] = value;
                    }
                    return value;
                }
                throw new KeyNotFoundException();
            }
            set
            {
                var entry = new Entry {Value = value, Counter = int.MinValue};
                lock (dict)
                {
                    //是否处于淘汰作业
                    if (recycleList == null)
                    {
                        //非淘汰作业下，容量超过上限
                        if (dict.Count >= Capacity)
                        {
                            //遍历，必须保持同步状态
                            recycleList = GetRecycleList();


                            ThreadPool.QueueUserWorkItem(Recycle);
                        }
                        //插入缓存项
                        dict[key] = entry;

                        //非淘汰过程时如存在缓冲表，则将缓冲表的数据加入主缓存表
                        if (recycleList == null && tempDict != null)
                        {
                            foreach (var keyValuePair in tempDict)
                            {
                                dict[keyValuePair.Key] = keyValuePair.Value;
                            }
                            tempDict = null;
                        }
                    }
                    else
                    {
                        //淘汰作业状态先加入缓冲表
                        if (tempDict == null)
                        {
                            tempDict = new Dictionary<K, Entry>(Capacity/10);
                        }
                        tempDict[key] = entry;
                    }
                }
            }
        }

        /// <summary>
        /// 目前只在主缓存中查找是否存在指定键
        /// </summary>
        public bool ContainsKey(K key)
        {
            return dict.ContainsKey(key);
        }

        /// <summary>
        /// 异步执行多余空间回收操作
        /// </summary>
        /// <param name="state"></param>
        private void Recycle(object state)
        {
            try
            {
                try
                {
                    //对待回收项预处理，用于取消移除列表中的任意项的执行。
                    //可能存在低性能操作，不应在同步任务中执行。
                    if (CacheItemsRecycledHandler != null)
                    {
                        CacheItemsRecycledHandler(recycleList);
                    }
                    //从缓存容器中移除
                    foreach (var keyValuePair in recycleList)
                    {
                        lock (dict)
                        {
                            Entry entry;
                            //如果项在回收过程中曾经被访问，不回收该项
                            if (dict.TryGetValue(keyValuePair.Key, out entry) && entry.Counter == int.MinValue)
                            {
                                dict.Remove(keyValuePair.Key);
                            }
                        }
                    }
                }
                finally
                {
                }
            }
            catch (Exception e)
            {
                log.Error(e);
            }
            finally
            {
                recycleList = null;
            }
        }


        private bool TryGetEntry(K key, out Entry entry)
        {
            if (dict.TryGetValue(key, out entry))
            {
                return true;
            }
            //主缓存未命中时，查询缓存表
            Dictionary<K, Entry> temp = tempDict;
            return temp != null && temp.TryGetValue(key, out entry);
        }

        /// <summary>
        /// 尝试获取一个缓存项，不调用CacheMissedHandler回调
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool TryGetValue(K key, out V value)
        {
            Entry entry;
            if (TryGetEntry(key, out entry))
            {
                value = entry.Value;
                return true;
            }
            value = default(V);
            return false;
        }

        /// <summary>
        /// 从缓存中移除一个项
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public bool Remove(K key)
        {
            lock (dict)
            {
                return dict.Remove(key);
            }
        }

        /// <summary>
        /// 获取要移除的项
        /// </summary>
        /// <returns></returns>
        private IList<KeyValuePair<K, V>> GetRecycleList()
        {
            var list = new SortedList<int, KeyValuePair<K, V>>(recyclingQuantity, new NoEqualComparer<int>(null));
            foreach (var pair in dict)
            {
                int counter = pair.Value.Counter;
                //重置计数器
                pair.Value.Counter = int.MinValue;
                //回收列表未满时添加
                if (list.Count < list.Capacity)
                {
                    list.Add(counter, new KeyValuePair<K, V>(pair.Key, pair.Value.Value));
                    continue;
                }
                //当前计数大于回收列表时跳过
                int lastIndex = list.Count - 1;
                if (counter >= list.Keys[lastIndex])
                {
                    continue;
                }

                //将当前项加入列表替换最后一项
                list.RemoveAt(lastIndex);
                list.Add(counter, new KeyValuePair<K, V>(pair.Key, pair.Value.Value));
            }
            return list.Values;
        }

        #region Nested type: Entry

        private class Entry
        {
            private int counter;
            private V value;

            public V Value
            {
                get
                {
                    Interlocked.Increment(ref counter);
                    return value;
                }
                set { this.value = value; }
            }

            public int Counter
            {
                get { return counter; }
                set { counter = value; }
            }
        }

        #endregion
    }
}